import javax.print.DocFlavor;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-17
 * Time:10:34
 */
public class TestDemo {
    //720. 词典中最长的单词

    /**
     * 给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，
     * 该单词是由 words 词典中其他单词逐步添加一个字母组成。
     * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static String longestWord(String[] words) {
        String ans = "";
        //先将所以words[i]存入集合中
        HashSet<String> hashSet = new HashSet<>(Arrays.asList(words));
        //遍历集合
        for (String s : hashSet) {
            int n = s.length();
            int m = ans.length();
            if (n < m) {
                continue;
            }
            //若其中有多个可行的答案，则返回答案中字典序最小的单词
            if (n == m && s.compareTo(ans) > 0) {
                continue;
            }
            boolean flag = true;
            //词典中其他单词逐步添加一个字母组成 所以答案substring的结果一定能从set中找到
            for (int i = 1; i <= n && flag; i++) {
                String sub = s.substring(0, i);
                if (!hashSet.contains(sub)) {
                    flag = false;
                }
            }
            if (flag) {
                ans = s;
            }
        }
        return ans;
    }

    //字典树/前缀树
    static int N = 30010, M = 26;
    static int[][] tr = new int[N][M];
    static boolean[] isEnd = new boolean[N];
    static int index = 0;

    void add(String s) {
        int p = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) {
                tr[p][u] = ++index;
            }
            p = tr[p][u];
        }
        isEnd[p] = true;
    }

    boolean search(String s) {
        int p = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) {
                return false;
            }
            p = tr[p][u];
        }
        return isEnd[p];
    }

    boolean startWith(String s) {
        int p = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) {
                return false;
            }
            p = tr[p][u];
        }
        return true;
    }

    //微信红包
    public int getValue(int[] gifts, int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int ans = 0;
        for (Integer num : gifts) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
                if (map.get(num) > (n / 2)) {
                    ans = num;
                    break;
                }
            } else {
                map.put(num, 1);
            }
        }
        return ans;
    }

    //计算字符串的编辑距离
    /**
     * 如果两个串的第一个字符相同 ，如A=xabcdae和B=xfdfa，只要计算
     * A[2,…,7]=abcdae和B[2,…,5]=fdfa的距离就可以了。
     * u 如果两个串的第一个字符不相同 ，那么可以进行如下的操作：
     * 1．删除A串的第一个字符，然后计算A[2,…,lenA]和B[1,…,lenB]的距离。
     * 2．删除B串的第一个字符，然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
     * 3．修改A串的第一个字符为B串的第一个字符，然后计算A[2,…,lenA]和B[2,…,lenB]的距离。
     * 4．修改B串的第一个字符为A串的第一个字符，然后计算A[2,…,lenA]和B[2,…,lenB]的距离。
     * 5．增加B串的第一个字符到A串的第一个字符之前，然后计算A[1,…,lenA]和B[2,…,lenB]的距离。
     * 6．增加A串的第一个字符到B串的第一个字符之前，然后计算A[2,…,lenA]和B[1,…,lenB]的距离。
     * <p>
     * 设Ai为字符串A(a1a2a3 … am)的前i个字符（即为a1,a2,a3 … ai）
     * 设Bj为字符串B(b1b2b3 … bn)的前j个字符（即为b1,b2,b3 … bj）
     * 设 L(i,j)为使两个字符串和Ai和Bj相等的最小操作次数。
     * 当ai==bj时 显然 L(i,j) = L(i-1,j-1)
     * 当ai!=bj时
     * 若将它们修改为相等，则对两个字符串至少还要操作L(i-1,j-1)次
     * 若删除ai或在bj后添加ai，则对两个字符串至少还要操作L(i-1,j)次
     * 若删除bj或在ai后添加bj，则对两个字符串至少还要操作L(i,j-1)次
     * 此时L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1
     * <p>
     * 显然，L(i,0)=i，L(0,j)=j, 再利用上述的递推公式，可以直接计算出L(i,j)值。
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String a = scanner.nextLine();
            String b = scanner.nextLine();
            System.out.println(leastDistance(a.toCharArray(), b.toCharArray()));
        }
    }

    private static int leastDistance(char[] strA, char[] strB) {
        int lengthA = strA.length;
        int lengthB = strB.length;
        int[][] len = new int[lengthA + 1][lengthB + 1];
        for (int i = 0; i < len.length; i++) {
            len[i][0] = i;
        }
        for (int i = 0; i < len[0].length; i++) {
            len[0][i] = i;
        }
        for (int i = 1; i < len.length; i++) {
            for (int j = 1; j < len[0].length; j++) {
                if (strA[i - 1] == strB[j - 1]) {
                    len[i][j] = len[i - 1][j - 1];
                } else {
                    len[i][j] = Math.min(Math.min(len[i - 1][j], len[i - 1][j - 1]), len[i][j - 1]) + 1;
                }
            }
        }
        return len[len.length - 1][len[0].length - 1];
    }
}
